 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return changeStr(s) == changeStr(t);
    }

    string changeStr(string str)
    {
        string ret;
        for (auto ch : str)
        {
            if (ch != '#') ret += ch;
            else
            {
                if (ret.size()) ret.pop_back();
            }
        }

        return ret;
    }
};

class Solution {
public:
    int calculate(string s) {
        vector<int> st;
        int n = s.size(), i = 0;
        char op = '+';

        while (i < n)
        {
            if (s[i] == ' ') i++;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                //将这个数字提取出来
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');

                if (op == '+') st.push_back(tmp);
                else if (op == '-') st.push_back(-tmp);
                else if (op == '*') st.back() *= tmp;
                else st.back() /= tmp;
            }
            else
            {
                op = s[i];
                i++;
            }
        }

        int ret = 0;
        for (auto x : st)
            ret += x;

        return ret;
    }
};

class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> strs;
        strs.push("");

        int i = 0, n = s.size();
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                nums.push(tmp);
            }
            else if (s[i] == '[')
            {
                //将括号后面的字符串提取出来
                i++;
                string tmp = "";
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                strs.push(tmp);
            }
            else if (s[i] == ']')
            {
                string tmp = strs.top();
                strs.pop();
                int k = nums.top();
                nums.pop();

                while (k--)
                {
                    strs.top() += tmp;
                }
                //跳过这个右括号
                i++;
            }
            else
            {
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                strs.top() += tmp;
            }
        }
        return strs.top();
    }
};

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0, n = popped.size();
        for (auto x : pushed)
        {
            st.push(x);
            while (st.size() && st.top() == popped[i])
            {
                st.pop();
                i++;
            }
        }

        return i == n;
    }
};